Lossless data compression is a category of data compression algorithms that facilitate exact recreation of original data from compressed data. One such type of lossless data compression algorithm is the Deflate compression algorithm. The Deflate algorithm is described in Request for Comment (“RFC”) 1951, entitled, “DEFLATE Compressed Data Format Specification v1.3,” published by the Network Working Group in May 1996. The Deflate algorithm compresses data through a two step process: 1) Lempel-Ziv (LZ77) coding followed by 2) Huffman coding.
LZ77 is a dictionary coding scheme that achieves compression by replacing data that appears several times within a dataset by (length, distance) pairs that point into a 32 KB sliding window of past output. When at least three consecutive bytes of data appear that already exist within the 32 KB sliding window, the bytes are replaced by a (length, distance) pair, where the length specifies how many bytes of data are repeated and the distance specifies how many bytes to look backwards in the sliding window for the beginning of the match. It is possible for distance>length, meaning that the match extends beyond the last byte of data stored in the sliding window at the start of the LZ77 decompression.
Following LZ77 coding, Huffman coding is applied. The LZ77 compressed data is encoded as prefix-free variable length Huffman codewords. These codewords are drawn from two distinct sets (also referred to as alphabets)—one for the lengths and literal codewords and another for the distance codewords. The literal codewords are codewords that are not part of a (length, distance) pair. The Huffman encoding achieves compression by replacing the most common words by short codewords and the least common words by long codewords.
The Deflate algorithm permits two types of Huffman encoding: static encoding and dynamic encoding. Static encoding uses two predefined Huffman codes, one for the lengths/literals and another for the distances, while the dynamic encoding uses two Huffman codes derived from the dataset itself.
The Deflate algorithm is used to compress a variety of data types and is the compression algorithm used in gzip data compression, PNG image files, and ZIP files. Conventional techniques for “decompressing” or “inflating” a data compressed with Deflate algorithm are software solutions. While inexpensive, these decompression solutions are limited in speed and are therefore less than ideal for high speed environments such as network appliances (e.g., routers, switches, traffic shapers/analyzers, etc.) or real-time hard-disk compression.